class MapSum {
    private static class TrieNode {
        TrieNode[] children=new TrieNode[26];
        int val=0;
    }
    private TrieNode root;
    public MapSum() {
        root=new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode p=root;
        int len=key.length();
        for(int i=0;i<len;i++) {
            char c=key.charAt(i);
            if(p.children[c-'a']==null) {
                p.children[c-'a']=new TrieNode();
            }
            p=p.children[c-'a'];
        }
        p.val=val;
    }
    private TrieNode getNode(TrieNode node,String prefix) {
        int len=prefix.length();
        for(int i=0;i<len;i++) {
            if(node==null) {
                return null;
            }
            char c=prefix.charAt(i);
           node=node.children[c-'a'];
        }
        return node;
    }
    public int sum(String prefix) {
        TrieNode p=getNode(root,prefix);
        if(p==null) {
            return 0;
        }
       
       int sum=0;
       travel(p,sum);
       return sum;
    }
    private void travel(TrieNode p,int sum) {
        if(p==null) {
            return ;
        }
        if(p.val!=0) {
            sum+=p.val;
        }
        for(int i=0;i<26;i++) {
            travel(p.children[i],sum);
        }
    }

    public static void main(String[] args) {
        MapSum map=new MapSum();
        map.insert("apple",3);
        map.sum("ap");
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */